/**
 * Clase Ejercicio 3: el del sapo que va saltando sobre las piedras
 */
package problem.ej3;


import java.util.Iterator;
import java.util.LinkedList;

import java.util.Vector;

import output.Problem3Output;
import test.TestEj3;




/**
 * @Class Ej3:
 * 
 *
 */
public class Ej3 {
	public static long contadorEj3;
	public static long contadorEj3_2; /*lo usaremos para sólo contar las operaciones de "existe_camino"*/
	/*
	 *@Método Algoritmo Principal: 
	 * Es donde acomodamos todos los parámetros de entrada para pasárselos a la función "buscarCamino" que es la que
	 * hace toda la "magia recursiva" de la programación dinámica.
	 * La lista de Xs e Ys tiene longitud par y cada posición "i" impar corresponde a un "X" e "i+1" a el "Y" correspondiente
	 * a ese "X"
	 */
	public static LinkedList<LinkedList<Integer>> algoritmo_ppal(Vector<Integer> vector_pos, int p,	int q, LinkedList<Integer> Xs_e_Ys){
		Vector<Tupla_pos_alcanzables> tronco = buscar_alcanzables(vector_pos, p, q);
		/*Asumo que ambos "x" e "y" corresponden a alguna posición válida*/
		LinkedList<LinkedList<Integer> > todos_los_caminos = new LinkedList<LinkedList<Integer> >();
		while(!Xs_e_Ys.isEmpty()){
			Integer X = Xs_e_Ys.poll();
			Integer Y = Xs_e_Ys.poll();
			int pos_X = buscar_pos_en_tronco(tronco, X);
			int pos_Y = buscar_pos_en_tronco(tronco, Y);
			LinkedList<Integer> camino = new LinkedList<Integer>();
			existe_camino(tronco, p, q, pos_X, pos_Y, camino);
			todos_los_caminos.add(camino);
			/*Los booleanos del tronco me quedaron cambiados, entonces para calcular con otro X y otro Y debo 
			 * volver a ponerlos en false*/
			todo_false(tronco);
		}
		return todos_los_caminos;
	}
	
	public static LinkedList<Integer> algoritmo_ppal_para_test(Vector<Integer> vector_pos, int p,	int q, Integer X, Integer Y){
		Vector<Tupla_pos_alcanzables> tronco = buscar_alcanzables(vector_pos, p, q);
		/*Asumo que ambos "x" e "y" corresponden a alguna posición válida*/
		contadorEj3+=1; /*la llamada de arriba*/
			int pos_X = buscar_pos_en_tronco(tronco, X);
			int pos_Y = buscar_pos_en_tronco(tronco, Y);
			LinkedList<Integer> camino = new LinkedList<Integer>();
			contadorEj3+=3; /*las llamadas de arriba*/
			existe_camino(tronco, p, q, pos_X, pos_Y, camino);
			contadorEj3+=1; /*la llamada de arriba*/
		contadorEj3+=1; /*el return de abajo*/
		return camino;
	}
	public static int buscar_pos_en_tronco(Vector<Tupla_pos_alcanzables> tronco, Integer pos){
		int res = 0; /*la inicialicé en 0 porque sino me tiraba error*/
		contadorEj3+=2; /*la llamada de arriba + la primer guarda del for*/
		for(int i = 0; i < tronco.size(); i++){
			contadorEj3+=1; /*la guarda de abajo*/
			if(tronco.elementAt(i).pos == pos){
				res = i;
				contadorEj3+=1; /*la ejecución*/
			}
			contadorEj3+=2; /*la iteración del for + la guarda del for*/
		}
		contadorEj3+=1; /*el return de abajo*/
		return res;
	}
		
	public static boolean existe_camino(Vector<Tupla_pos_alcanzables> tronco, int p, int q, int pos_X, int pos_Y, LinkedList<Integer> camino){
		int X = tronco.elementAt(pos_X).pos;
		int Y = tronco.elementAt(pos_Y).pos;
		contadorEj3+=3; /*las llamadas de arriba que son O(1) + la guarda del if de abajo*/
		contadorEj3_2+=3; /*las llamadas de arriba que son O(1) + la guarda del if de abajo*/
		if(es_alcanzable(p, q, X, Y)){
			camino.add(tronco.elementAt(pos_X).pos);
			camino.add(tronco.elementAt(pos_Y).pos);
			contadorEj3+=3; /*ambos add + el return*/
			contadorEj3_2+=3; /*ambos add + el return*/
			return true;
		}
		else{
			/*Tengo que hacer llamadas recursivas. Primero marco a esta posición como que la estoy recorriendo
			 * (para que si alguna llamada recursiva llama de nuevo a estos "X" e "Y", que no lo calcule porque me
			 * metería en un loop infinito)
			 * Como el Y es SIEMRE el mismo en todas las llamadas rescursivas (el único que va cambiando es el X)
			 * entonces puedo simplemente cambiar el booleano en la posición correspondiente al X*/
			tronco.elementAt(pos_X).la_estoy_recorriendo = true;
			
			LinkedList<Integer> alcanzables_por_X = tronco.elementAt(pos_X).alcanzables;
			Iterator<Integer> list_it = alcanzables_por_X.iterator();
			contadorEj3+=4; /*las llamadas de arriba + la primer guarda del while*/
			contadorEj3_2+=4; /*las llamadas de arriba + la primer guarda del while*/
			
			while(list_it.hasNext()){
				int pos_Xi = list_it.next().intValue();
				contadorEj3+=2; /*la llamada de arriba + la guarda de abajo*/
				contadorEj3_2+=2; /*la llamada de arriba + la guarda de abajo*/
				if(!(tronco.elementAt(pos_Xi).la_estoy_recorriendo) && !(tronco.elementAt(pos_Xi).ya_la_recorrí)){
					/*Si a esta llamada recursiva no la estoy tratando de resolver ahora o si ya la resolvi y no dio
					 * camino posible, que haga más llamdas recursivas*/
					contadorEj3+=1; /*la guarda del if de abajo*/
					contadorEj3_2+=1; /*la guarda del if de abajo*/
					if(!(existe_camino(tronco, p, q, pos_Xi, pos_Y, camino))){
						/*osea, si no encontró solución esa llamada recursiva, entonces marco como que no 
						 * existe camino entre Xi e Y*/ 
						tronco.elementAt(pos_Xi).ya_la_recorrí = true;
						contadorEj3+=1; /*asignación*/
						contadorEj3_2+=1; /*asignación*/
					}
					else{
						/*Si encontró un camino, que deje de ejecutar y lo devuelva (busco algún camino, no el mejor)*/
						camino.addFirst(tronco.elementAt(pos_X).pos);
						contadorEj3+=2; /*el add y el return*/
						contadorEj3_2+=2; /*el add y el return*/
						return true;
					}
				}
			}
			/*Si recorrió todos los Xi (los alcanzables por X) y ninguno puede llegar a Y, que devuelva false*/
			contadorEj3+=1; /*el return de abajo*/
			contadorEj3_2+=1; /*el return de abajo*/
			return false;
		}
	}
	public static boolean es_alcanzable(int p, int q, int X, int Y){
		int min,max;
		contadorEj3+=3; /*inicializaciones de arriba+guarda abajo*/
		if(p < q){
			min = p;
			max = q;
			contadorEj3+=2; /*2 operaciones*/
		}
		else{
			min = q;
			max = p;
			contadorEj3+=2; /*2 operaciones*/
		}
		contadorEj3+=2; /*la guarda + el return de abajo*/
		if( (Math.abs(X-Y)< min) || (Math.abs(X-Y)> max)) return false;
		else return true;
	}
	
	public static Vector<Tupla_pos_alcanzables> buscar_alcanzables(Vector<Integer> vector_pos, int p, int q){
		int max;
		contadorEj3+=2; /*inicialización arriba + guarda abajo*/
		if(p < q){
			max = q;
		}
		else max = p;
		contadorEj3+=1; /*asignación del if o del else*/
		Vector<Tupla_pos_alcanzables> tronco = new Vector<Tupla_pos_alcanzables>(vector_pos.size());
		contadorEj3+=vector_pos.size(); /*inicialización de tronco*/
		contadorEj3+=1; /*guarda del for de abajo*/
		for(int i = 0; i < vector_pos.size(); i++){
			int Y = vector_pos.elementAt(i);
			Tupla_pos_alcanzables tupla = new Tupla_pos_alcanzables();
			tupla.la_estoy_recorriendo = false;
			tupla.ya_la_recorrí = false;
			tupla.pos = Y;
			LinkedList<Integer> alcanzables = new LinkedList<Integer>();
			boolean termine = false;
			contadorEj3+=7; /*7 asignaciones arriba*/
			
			/*Primero busco los alcanzables a izquierda*/
			int j = i-1;
			contadorEj3+=2; /*asignación arriba y guarda abajo*/
			while((j>=0) && !(termine)){
				/*Quiero ver si los j pueden alcanzar a i*/
				int X = vector_pos.elementAt(j);
				contadorEj3+=2; /*asignación arriba y guarda abajo*/
				if(es_alcanzable(p, q, X, Y)){
					alcanzables.add((Integer)j);
					contadorEj3+=1; /*asignación arriba*/
				}
				else{
				 	contadorEj3+=1; /*guarda abajo*/
					if(Math.abs(X-Y)> max){
						/*Si ya me alejé demasiado, no tiene sentido seguir alejándome, entonces que termine
						 * con este j y pase al anterior si hay anterior*/
						termine = true;
						contadorEj3+=1; /*asignación arriba*/
					}
				}
				j--; /* si no terminó, que pase al anterior (la guarda del while mira si hay anterior
					  * o si no terminó)*/
				contadorEj3+=2; /*asignación arriba + de nuevo guarda while*/
			}
			/*Ya agregué todas las posiciones alcanzables por izquierda. Ahora busco las alcanzables por derecha. */
			termine = false;
			j = i+1;
			contadorEj3+=3; /*2 asignaciones arriba + guarda abajo*/
			
			while((j<vector_pos.size()) && !(termine)){
				/*Quiero ver si los j pueden alcanzar a i, y si pueden, los agrego a la lista*/
				int X = vector_pos.elementAt(j);
				contadorEj3+=2; /*asignación arriba + guarda abajo*/
				if(es_alcanzable(p, q, X, Y)){
					alcanzables.add((Integer)j);
					contadorEj3+=1; /*asignaciones arriba*/
				}
				else{
					contadorEj3+=1; /*guarda abajo*/
					if(Math.abs(X-Y)> max){
						/*Si ya me alejé demasiado, no tiene sentido seguir alejándome, entonces que termine
						 * con este j y pase al siguiente si hay siguiente*/
						termine = true;
						contadorEj3+=1; /*asignaciones arriba*/
					}
				}
				j++; /* si no terminó, que pase al siguiente (la guarda del while mira si hay siguiente
					  * o si no terminó)*/
				contadorEj3+=2; /*asignaciones arriba + de nuevo guarda while*/
			}
			tupla.alcanzables = alcanzables;
			tronco.add(tupla);
			contadorEj3+=3; /*2 asignaciones arriba + de nuevo guarda for*/
		}
		return tronco;
	}
	public static void todo_false(Vector<Tupla_pos_alcanzables> tronco){
		for(int i = 0; i<tronco.size();i++){
			Tupla_pos_alcanzables tupla = tronco.elementAt(i);
			tupla.la_estoy_recorriendo = false;
			tupla.ya_la_recorrí = false;
		}
	}

		
	
	public static void main(String[] args) throws Exception{
		Problem3Output.deListaAArchivo(TestEj3.generarTestUnMovimiento(700), "./src/resources/Tp2Ej3.UnMov.in");
		Problem3Output.deListaAArchivo(TestEj3.generarTestPrimeroConUltimo(700), "./src/resources/Tp2Ej3.PrimeroConUltimo.in");
		TestEj3.testRendimiento("./src/resources/Tp2Ej3.UnMov.in");
		TestEj3.testRendimiento("./src/resources/Tp2Ej3.PrimeroConUltimo.in");
		TestEj3.testRendimiento_existe_camino("./src/resources/Tp2Ej3.UnMov.in");
		TestEj3.testRendimiento_existe_camino("./src/resources/Tp2Ej3.PrimeroConUltimo.in");
		
		
	}

}
